package com.zxy.leetcode._00000_00099._00060_00069;

/**
 * https://leetcode-cn.com/problems/minimum-path-sum/
 *
 * 最小路径和
 * 给定一个包含非负整数的 m x n 网格 grid ，
 * 请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 * 说明：每次只能向下或者向右移动一步。
 *
 * 标签：动态规划
 */
public class Test00064 {

    public static void main(String[] args) {
        Test00064 test = new Test00064();

        int[][] grid = {
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        };
        System.out.println(test.minPathSum(grid));
    }

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = grid;

        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (i==0 && j==0) {
                    continue;
                }
                if (i==0) {
                    dp[i][j] = dp[i][j-1] + dp[i][j];
                }else if (j==0) {
                    dp[i][j] = dp[i-1][j] + dp[i][j];
                }else {
                    dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + dp[i][j];
                }
            }
        }

        return dp[m-1][n-1];
    }
}
